import java.util.*;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-763-划分字母区间
 * @date 2025/7/23 16:59
 */
public class Solution763 {
    public List<Integer> partitionLabels(String s) {
        int[] lastPos = new int[26];

        // 确定每个元素的最后出现位置
        for (int i = 0; i < s.length(); i++) {
            lastPos[s.charAt(i) - 'a'] = i;
        }

        int start = 0;
        int end = 0;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, lastPos[s.charAt(i) - 'a']);
            if (i == end) {
                ans.add(end - start + 1);
                start = end + 1;
            }
        }

        return ans;
    }

}
